package _interview75;

/**
 * 724. 寻找数组的中心下标
 */
public class No724 {
    /**
     * 1. O(2n)空间复杂度
     */
    public int pivotIndex1(int[] nums) {
        int n = nums.length;

        int[] preArr = new int[n];
        for (int i = 1; i < n; i++) {
            preArr[i] = preArr[i - 1] + nums[i - 1];
        }

        int[] sufArr = new int[n];
        for (int i = n - 1 - 1; i >= 0; i--) {
            sufArr[i] = sufArr[i + 1] + nums[i + 1];
        }

        for (int i = 0; i < n; i++) {
            if (preArr[i] == sufArr[i]) return i;
        }
        return -1;
    }

    /**
     * 2. O(n)空间复杂度
     */
    public int pivotIndex2(int[] nums) {
        int n = nums.length;

        int[] sufArr = new int[n];
        for (int i = n - 1 - 1; i >= 0; i--) {
            sufArr[i] = sufArr[i + 1] + nums[i + 1];
        }

        if (sufArr[0] == 0) return 0;
        int preSum = 0;
        for (int i = 1; i < n; i++) {
            preSum += nums[i - 1];
            if (preSum == sufArr[i]) return i;
        }

        return -1;
    }
}
